package com.yulongtian.oneProblemEveryDay.month202212;

import java.util.Arrays;

/**
 * https://leetcode.cn/problems/equal-sum-arrays-with-minimum-number-of-operations/
 * 可
 *
 * @author yulongTian
 * @create 2022-12-07 10:27
 */
public class Test03 {
    public static void main(String[] args) {
        System.out.println(minOperations(new int[]{6, 6}, new int[]{1}));

    }

    public static int minOperations(int[] nums1, int[] nums2) {
        int len1 = nums1.length;
        int len2 = nums2.length;

        //不能相等
        if (len1 > len2 * 6 || len2 > len1 * 6) {
            return -1;
        }


        //分别计算原始的总和  并计数
        int initSum1 = 0;
        int initSum2 = 0;

        for (int i : nums1) {
            initSum1 += i;
        }

        for (int i : nums2) {
            initSum2 += i;
        }

        int diff = initSum2 - initSum1;// 数组元素和的差，我们要让这个差变为 0

        if (diff == 0) {
            return 0;
        }

        if (diff < 0) {
            diff = -diff;
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = temp;//交换，统一让 nums1 的数变大，nums2 的数变小
        }

        int[] cnt = new int[6];//统计每个数的最大变化量
        for (int i : nums1) {
            cnt[6 - i]++;// nums1 的变成 6
        }
        for (int i : nums2) {
            cnt[i - 1]++;//nums2 的变成 1
        }
        //从大到小枚举最大变化量 5 4 3 2 1
        for (int i = 5, ans = 0; ; i--) {
            if (i * cnt[i] >= diff) {//可以让 d 变为 0
                return ans + (diff + i - 1) / i;
            }
            ans += cnt[i];//需要所有最大变化量为 i 的数
            diff -= i * cnt[i];
        }


    }
}
